Search results for "Mixed rural postman problem"

showing 3 items of 3 documents

A comparison of two different formulations for Arc Routing Problems on Mixed graphs

2006

[EN] Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented.

Arc routingGeneral Computer ScienceLinear programmingMixed Chinese postman problemMixed graphMixed rural postman problemManagement Science and Operations ResearchRoute inspection problemTree traversalModeling and SimulationEnhanced Data Rates for GSM EvolutionRouting (electronic design automation)Mixed general routing problemMATEMATICA APLICADAAlgorithmArc routingMathematicsVariable (mathematics)
researchProduct

The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm

2017

[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters.

Information Systems and ManagementHierarchical Routing ProblemsGeneral Computer Science0211 other engineering and technologiesMixed graph02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringCombinatorics0502 economics and businessOrder (group theory)Mixed Rural Postman ProblemPolyhedral analysisBranch-and-cut Hierarchical Routing Problems Mixed Rural Postman Problem Polyhedral analysis Modeling and Simulation Management Science and Operations Research Information Systems and ManagementMathematicsDiscrete mathematics050210 logistics & transportation021103 operations research05 social sciencesBranch-and-cutModeling and SimulationBenchmark (computing)Polyhedral analysisMATEMATICA APLICADABranch and cutAlgorithmEuropean Journal of Operational Research
researchProduct

New Results on the Mixed General Routing Problem

2005

[EN] In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. …

Mathematical optimizationmedicine.medical_specialtyBranch and boundPolyhedral combinatoricsMixed graphHoneycomb (geometry)Mixed rural postman problemManagement Science and Operations ResearchPolyhedral combinatoricsComputer Science ApplicationsRural postman problemVehicle routing problemmedicineDestination-Sequenced Distance Vector routingRouting (electronic design automation)General routing problemMATEMATICA APLICADACutting-plane methodMathematics
researchProduct